//插值查找
#include <stdio.h>
#include <stdlib.h>
int interpolationsearch(int arr[],int length,int key);
void input(int add[],int size);
int main(){
	int len;
	int i=0;
	printf("please enter the array length:");
	scanf("%d",&len);
//动态分配内存，因为数组的长度必须是常量（确定的），因为在编译时就要确定数组长度
	int * add=(int*)malloc(len*sizeof(int));
//内存可能会分配失败，返回非 0的数，终止程序
	if(add==NULL)
	{
		printf("Memory allocation failed");
		return 1;
	}
//调用输入函数
	printf("\nplease enter a ordered array:\n");
	input(add,len);
	int skey=0;
	printf("\nplease enter a number for searching:\n");
	scanf("%d",&skey);
//调用插值查找函数
	int index=interpolationsearch(add,len,skey);
	if(index==-1)
		printf("No Find!");
	else
		printf("the index of the searched value is %d",index);
	free(add);
	return 0;
	}
int interpolationsearch(int arr[],int size,int key)
{
	int min=0;
	int max=size-1;
	while(min<=max){
		//插值查找的公式
		//就是key值在"直方条"中的占比乘上当前总长度(也就是计算在该直方图横坐标的长度）加上开头数值（不一定从0开始）
		int mid=min+(((key-arr[min])/(arr[max]-arr[min]))*(max-min));
		if(arr[mid]>key)
			max=mid-1;
		else if(arr[mid]<key)
			min=mid+1;
		else
			return mid;
	}
	return -1;
}
void input(int add[],int size){
	int i=0;
		for(i=0;i<size;i++){
		printf("NO.%d: ",i);
		scanf("%d",&add[i]);
		if(i>0&&add[i]<add[i-1])
			{
				printf("\nplease enter a number great than previous one:\n");
				--i; 
			}
		}
}
